package days30.title112;

class Solution {
    boolean flag;
    int treeSum = 0;
    int targetSum = 0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root==null)
            return false;
        this.targetSum = targetSum;
        dfs(root);
        return flag;
    }

    private void dfs(TreeNode root) {
        if (root!=null){
            treeSum+=root.val;
            if (targetSum==treeSum&&root.right==null&&root.left==null){
                flag = true;
            }
            dfs(root.right);
            if (root.right!=null)
                treeSum-=root.right.val;
            dfs(root.left);
            if (root.left!=null)
                treeSum-=root.left.val;
        }

    }
}